package a.codetop;

import org.junit.Test;
import 其他.DataStructure.TreeNode;

public class _11前序和中序造树 {
    @Test
    public void test() {
        int[] pre = {1,2}, zhong={2,1};
        buildTree(pre,zhong);
    }

    //q前序 z中序
    int[] q,z;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        q=preorder;z=inorder;
        int qL=0,qR=q.length-1,zL=0,zR=z.length-1;
        return back(qL,qR,zL,zR);
    }

    private TreeNode back(int qL, int qR, int zL, int zR) {
        //N
        if(
            //0n都要封住，因为+1-1都有
            qL<0||qL>=q.length ||
            zL<0||zL>=z.length ||
            qR<0||qR>=q.length ||
            zR<0||zR>=z.length ||
            //这个要背
            qL>qR || zL>zR
        ) return null;
        //前序剩一个叶子
        if(qL==qR) return new TreeNode(q[qL]);

        //盯住一个方框+双闭区间(每次删m)+0用L,n用R代替，就不会乱
        //向下找m
        int rotVal = q[qL];
        int z_ind = findValInd(zL,zR,rotVal);
        int lf_zL = zL, lf_zR = z_ind-1; int rt_zL = z_ind+1, rt_zR = zR;
        //向上拆
        int lf_qL = qL+1, lf_qR = qL+z_ind-zL; int rt_qL = lf_qR+1, rt_qR = qR;

        //rot指向中序序列中的某个节点
        TreeNode rot = new TreeNode(rotVal);
        rot.left = back(lf_qL,lf_qR,lf_zL,lf_zR);
        rot.right = back(rt_qL,rt_qR,rt_zL,rt_zR);
        return rot;
    }

    private int findValInd(int zL, int zR, int rotVal) {
        for (int i = zL; i <= zR; i++) {
            if(z[i]==rotVal){
                return i;
            }
        }
        return -1;
    }

}
